package 剑指Offer.medium;

import java.util.Deque;
import java.util.LinkedList;

public class 股票的最大利润 {
    class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length < 2) return 0;
            Deque<Integer> queue = new LinkedList<>();
            int max = 0;
            queue.addLast(prices[0]);
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] >= queue.peekLast()) {
                    queue.addLast(prices[i]);
                } else {
                    max = Math.max(max, queue.peekLast() - queue.peekFirst());
                    while (!queue.isEmpty() && queue.peekLast() < prices[i]) {
                        queue.pollLast();
                    }
                    queue.addLast(prices[i]);
                }
            }
            return Math.max(max, queue.peekLast() - queue.peekFirst());
        }
    }
}
